package com.dmall.play.interview.chapter09;

import java.util.ArrayList;
import java.util.List;

/**
 * 记忆化搜索
 */
public class Leetcode120V4 {

    private int[][] dp = null;

    public int minimumTotal(List<List<Integer>> triangle) {
        dp = new int[triangle.size()][triangle.size()];
        dp[0][0] = triangle.get(0).get(0);
        for (int row = 1; row < triangle.size(); row++) {
            List<Integer> cols = triangle.get(row);
            for (int col = 0; col < cols.size(); col++) {
                if (col == 0) {
                    dp[row][0] = dp[row - 1][0] + triangle.get(row).get(col);
                } else if (col == row) {
                    dp[row][col] = dp[row - 1][col - 1] + triangle.get(row).get(col);
                } else {
                    dp[row][col] = Math.min(dp[row - 1][col], dp[row - 1][col - 1]) + triangle.get(row).get(col);
                }
            }
        }
        int[] minPathArr = dp[triangle.size() - 1];
        int minPathTotal = Integer.MAX_VALUE;
        for (int minNum : minPathArr) {
            minPathTotal = Math.min(minPathTotal, minNum);
        }
        return minPathTotal;
    }

    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        List<Integer> item1 = new ArrayList<>();
        item1.add(2);
        List<Integer> item2 = new ArrayList<>();
        item2.add(3);
        item2.add(4);
        List<Integer> item3 = new ArrayList<>();
        item3.add(6);
        item3.add(5);
        item3.add(7);
        List<Integer> item4 = new ArrayList<>();
        item4.add(4);
        item4.add(1);
        item4.add(8);
        item4.add(3);
        triangle.add(item1);
        triangle.add(item2);
        triangle.add(item3);
        triangle.add(item4);

        Leetcode120V4 leetcode120 = new Leetcode120V4();
        System.out.println(leetcode120.minimumTotal(triangle));
    }
}
